package LeetCode;

import com.company.Tree.Tree;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}9:47
 */
public class LeetCode110 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public boolean isBalanced(TreeNode root) {

        return level(root) != -1;
    }


    //自底向上 相当于后序遍历
    public int level(TreeNode root){
      if (root == null){
          return 0;
      }
      int left = level(root.left);
      if (left == -1){
          return -1;
      }
      int right = level(root.right);
      if (right == -1){
          return -1;
      }
      return Math.abs(left - right) < 2 ? Math.max(right,left) + 1 : -1;
    }

    //自上到下
    public boolean isBalanced2(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) < 2 && isBalanced2(root.left) && isBalanced2(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

    public boolean isBalanced3(TreeNode root){
        if (root == null){
            return true;
        }
        return Math.abs(depth(root.left) - depth(root.right)) < 2 && isBalanced3(root.left) && isBalanced3(root.right);
    }

}
